package code.oldCode.feishuSpecializedTraining.binary_tree;

import utils.TreeNode;

public class MyBinaryTree7 {
    // 236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor236(TreeNode root, TreeNode p, TreeNode q) {
        // 如果当前节点就是p或者q，则返回p或者q，没找到就是null
        if (root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor236(root.left, p, q);
        TreeNode right = lowestCommonAncestor236(root.right, p, q);
        if (left != null && right != null) // 左右都找到了，说明公共祖先就是当前节点
            return root;
        else if (left != null)
            return left;
        else
            return right;
    }

    // 235. 二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor235(TreeNode root, TreeNode p, TreeNode q) {
        // 与上一题类似，找到即返回
        if (root == null || root == p || root == q)
            return root;
        // 不同的是，由于是搜索树，故根据pq的值，可以限制root是否正确，当root在pq值范围内时，说明左右各一个，root就是公共祖先
        // 与上一题对比的剪枝是：不必左右都遍历一遍了~
        if (Math.min(p.val, q.val) < root.val && root.val < Math.max(p.val, q.val))
            return root;
        else if (root.val > Math.max(p.val, q.val))
            return lowestCommonAncestor235(root.left, p, q);
        else
            return lowestCommonAncestor235(root.right, p, q);
    }

    // 701. 二叉搜索树中的插入操作
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        TreeNode node = root;
        while (true) {
            int nowVal = node.val;
            if (nowVal < val) {
                if (node.right == null) {
                    node.right = new TreeNode(val);
                    return root;
                } else {
                    node = node.right;
                }
            } else {
                if (node.left == null) {
                    node.left = new TreeNode(val);
                    return root;
                } else {
                    node = node.left;
                }
            }
        }
    }
}
